class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 要解决这道题目需要理解什么是祖先节点，已经什么是最近的公共祖先节点
        // 祖先节点的定义就是若一个节点p在节点root的左右子树种，或者p节点就是root节点，则roor是p的祖先
        // 最近公共祖先的定义就是，若root是p和q的祖先节点，并且root的左子树和右子树都不是p和q的公共祖先那么
        // root就是最近的公共祖先
        // 根据上面的定义如果某一个root节点是p和q的最近公共祖先那么q和p在root的子树种，并且一个在左子树一个在右子树
        // 第二种情况p节点就是最近公共祖先，那么q就是p的左右子树中的节点
        // 第三种情况q为最近公共祖先，那么p就是q左右子树中的节点
        // 现在就是去寻找是否存在节点满足这三个条件中的一个那么这个节点就是最后的答案节点、
        if(root == nullptr||root == p||root == q)
        {
            //如果节点为nullptr或者当前节点为p或者q返回
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left,q,p);
        TreeNode* right = lowestCommonAncestor(root->right,q,p);
        if(left == nullptr)
        {
            //说明这个节点的左子树中没有qp节点，最近公共祖先就在右子树中
            return right;
        }
        if(right == nullptr)
        {
            return left;//同上
        }
        //否则到这里说明该节点的左子树中存在p，以及右子树中存在节点q，或者该节点为p，左右子树中存在q
        //或者该节点为q,左右子树中存在节点p
        return root;
    }
};